Scholes có trận đấu quốc tế đầu tiên gặp Nam Phi năm 1997 trong trận giao hữu thắng 2–1 trên sân Old Trafford, và được gọi vào đội tuyển Anh tham dự World Cup 1998. Tại giải này, đội tuyển Anh nằm cùng bảng với Colombia, Tunisia và Romania. Trong trận đấu vòng bảng gặp Tunisia, Scholes là người ấn định chiến thắng 2–0. Tuy nhiên đội tuyển Anh bị loại khỏi World Cup 1998 bởi Argentina trên chấm phạt đền ở vòng knock-out thứ nhất.

Ngày 27 tháng 3 năm 1999, Scholes lập hat-trick cho đội tuyển Anh trong trận gặp Ba Lan. Ngoài ra, Scholes đã ghi cả hai bàn trong chiến thắng 2–0 của đội tuyển Anh trên sân Hampden Park trước Scotland trong trận lượt đi play-off Euro 2000, ấn định tổng tỉ số 2–1 và giành quyền vào vòng chung kết. Trong trận đấu vòng loại gặp Thụy Điển vào tháng 6, Scholes trở thành cầu thủ Anh đầu tiên và cuối cùng bị đuổi khỏi sân trong một trận đấu quốc tế trên sân vận động Wembley cũ.[16]

Bước sang thế kỉ XXI, Scholes trở thành một cầu thủ nổi bật trong hàng tiền vệ của đội Anh, là sự lựa chọn hàng đầu cho World Cup 2002. Mặc dù vậy, sau giải đấu, Scholes nhận thấy cơ hội của anh ở đội tuyển đã giảm xuống do huấn luyện viên Sven-Göran Eriksson thường sắp xếp anh chơi ở vị trí tiền vệ cánh trái để hỗ trợ cho bộ đôi Steven Gerrard và Frank Lampard ở trung tâm.[75] Scholes tuyên bố giã từ sự nghiệp thi đấu quốc tế vào tháng 8 năm 2004, viện dẫn rằng cuộc sống gia đình của anh và sự nghiệp với câu lạc bộ Manchester United quan trọng hơn.[76]

Tháng 7 năm 2006, sau sự ra đi của Eriksson, Scholes có đề cập đến chuyện có thể tiếp tục thi đấu cho đội tuyển quốc gia dưới sự huấn luyện của Steve McClaren, tuy nhiên điều đó đã không bao giờ xảy ra.[77] Vào tháng 5 năm 2010, huấn luyện viên Fabio Capello, người kế nhiệm McClaren, đã tiếp xúc với Scholes để thuyết phục anh trở lại đội tuyển trước thềm World Cup 2010, nhưng anh từ chối và nói rằng muốn dành thời gian cho gia đình.[78] Vào ngày 7 tháng 6 năm 2010, Scholes tiết lộ rằng nếu Capello cho anh nhiều thời gian hơn và hỏi anh sớm hơn thì có lẽ anh đã nhận lấy cơ hội.[79] Ngày 27 tháng 7 năm 2010, Scholes bày tỏ sự hối tiếc vì đã không nhận lấy cơ hội thi đấu thêm một giải World Cup nữa, nói rằng rất có thể anh đã phạm sai lầm.[80]

Bàn thắng quốc tế